題目

看似過著四天連假的生活，其實你已規劃好一連串的旅遊。但車票只有3種:1、7、30天通行票，怎樣才能最省呢!?

• 給定2個array，稱作days和costs
• days存了你哪天要出遊。
• costs存了3種票的價錢。
• Note
  • 1 <= days.length <= 365
  • 1 <= days[i] <= 365
  • days is in strictly increasing order.
  • costs.length == 3
  • 1 <= costs[i] <= 1000
• Example
  • days = [1,4,6,7,8,20], costs = [2,7,15]
  • 代表你在第1、4、6、7、8天與第20天要出門玩!
  • 1天票是2元，7天票是7元，30天票是15元
  • 最省的買法是
    • 第一天買1天票-->2元
    • 第四天買7天票，涵蓋4、6、7、8-->7元
    • 第20天再買一天票-->2元。
  • 共11元，回傳11。

解法

使用動態規劃法，

• 因為days為嚴格遞增，days最後一格會是最大天數，我們以最大天數+1的大小創一個array稱為dp。
  *這邊多+1僅是為了方便，因為程式中index從0開始，+1能讓我們第1天對到的是dp[1]，第二天對到的是dp[2]。
• 我們從第一天(i=1)開始!如果碰到了要出遊的那一天(i==days[j])，我們就比較一下。各種票+先前對應天數已花的錢，哪個最小，我們就存哪個到當前這天的dp[i]。
  • costs[0]是1天票，所以加前一天所花的錢。
  • costs[1]是7天票，所以加前7天所花的錢。 min(i,7)則是避免超出index範圍。
  • costs[2]是30天票，所以加前30天所花的錢。 min(i,30)則是避免超出index範圍。
• 阿如果今天不是要出遊的天(i!=days[j])，我們就儲存昨天的值到今天(dp[i]=dp[i-1])，因為還沒花到錢嘛!
• 如此下去，dp最後一格儲存的值(dp.back())即會是我們花最少的錢。

Code

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        vector<int> dp(days.back() + 1, 0);
        
        for (int i = 1, j = 0; i <= dp.size()-1; i++) {
            if (i == days[j]) {
                // moving j to the next number
                j++;
                comparsion
                dp[i] = min({ 
                    costs[0] + dp[i - 1], 
                    costs[1] + dp[i - min(i, 7)],
                    costs[2] + dp[i - min(i, 30)], });
            }
            else {
            
                dp[i] = dp[i - 1];
            }
        }
        return dp.back();
    }
};